#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto &x : v) cin >> x;
  vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
  for (int l = n - 1; l >= 0; l --) {
    dp[l][l] = v[l] * n;
    for (int r = l + 1; r < n; r ++) {
      int day = n - (r - l);
      dp[l][r] = max(dp[l + 1][r] + v[l] * day,
                     dp[l][r - 1] + v[r] * day);
    }
  }
  cout << dp[0][n - 1] << endl;
}